#include <iostream>
#include <algorithm>
#include <assert.h>

using namespace std;

namespace own
{
	template<class T>
	struct listNode
	{
		T _data;

		listNode<T>* _next;
		listNode<T>* _prev;

		listNode(const T& data = T())
			:_data(data)
			,_next(nullptr)
			,_prev(nullptr)
		{}
	};

	template<class T,class ptr,class ref>
	struct listIterator
	{
		typedef listNode<T> Node;
		typedef listIterator<T, ptr, ref> self;

		Node* _node;

		listIterator(Node* node)
			:_node(node)
		{}

		//++it
		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		self operator++(int)
		{
			self tmp(_node);
			_node = _node->_next;
			return tmp;
		}

		self& operator--()
		{
			_node = _node->_prev;
			return  *this;
		}

		self operator--(int)
		{
			self tmp(_node);
			_node = _node->_prev;
			return tmp;
		}

		ref operator*()
		{
			return _node->_data;
		}

		ptr operator->()
		{
			return &_node->_data;
		}

		bool operator!=(const self& it)
		{
			return _node != it._node;
		}

		bool operator==(const self& it)
		{
			return _node == it._node;
		}

	};


	template<class T>
	class list
	{
		typedef listNode<T> Node;
	public:
		typedef listIterator<T, T*, T&> iterator;
		typedef listIterator<T, const T*, const T&> const_iterator;
		list()
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;
		}

		iterator begin()
		{
			return iterator(_head->_next);
		}

		iterator end()
		{
			return iterator(_head);
		}

		const_iterator begin() const
		{
			return const_iterator(_head->_next);
		}

		const_iterator end() const
		{
			return const_iterator(_head);
		}

		void push_back(const T& val = T())
		{
			Node* newnode = new Node(val);
			Node* tail = _head->_prev;

			tail->_next = newnode;
			newnode->_prev = tail;
			newnode->_next = _head;  
			_head->_prev = newnode;


			//insert(end(), val);
		}

		void pop_back()
		{
			erase(--end());
		}

		void push_front(const T& val = T())
		{
			insert(begin(), val);
		}

		void pop_front()
		{
			erase(begin());
		}

		iterator insert(iterator pos ,const T& val)
		{
			Node* cur = pos._node;
			Node* newnode = new Node(val);
			Node* prev = cur->_prev;

			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;

			return iterator(newnode);
		}

		iterator erase(iterator pos)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;

			prev->_next = next;
			next->_prev = prev;

			delete cur;

			return iterator(next);
		}

	private:

		Node* _head = nullptr;
	};

	void test_list01()
	{
		list<int> first;
		for (int i = 0; i < 4; i++)
		{
			first.push_back(i);
		}

		//ListIterator<int> it = first.begin();
		list<int>::iterator it = first.begin();
		while (it != first.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

		for (auto e : first)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	struct pos
	{
		int _row;
		int _col;

		pos(int row = 0, int col = 0)
			:_row(row)
			, _col(col)
		{}

	};

	void test_list02()
	{
		list<pos> It1;
		It1.push_back(pos(100, 200));
		It1.push_back(pos(300, 400));
		It1.push_back(pos(500, 600));
		list<pos>::iterator it = It1.begin();
		while (it != It1.end())
		{
			cout << (*it)._col << (*it)._row << " ";
			cout << it->_col << it->_row << " ";
			++it;
		}
		cout << endl;
	}

	void Fun(const list<int>& lt)
	{
		list<int>::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

	}

	void test_list03()
	{
		list<int> It2;
		It2.push_back(1);
		It2.push_back(2);
		It2.push_back(3);

		Fun(It2);
	}

	void test_list04()
	{
		list<int> It3;
		It3.push_back(1);
		It3.push_back(2);
		It3.push_back(3);

		It3.insert(It3.begin(), 100);

		It3.push_back(1);
		It3.push_back(2);
		It3.push_back(3);
		It3.erase(++It3.begin());
		list<int>::iterator it = It3.begin();
		while (it != It3.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

		It3.pop_back();
		list<int>::iterator it2 = It3.begin();
		while (it2 != It3.end())
		{
			cout << *it2 << " ";
			++it2;
		}
		cout << endl;


		It3.push_front(200);
		list<int>::iterator it3 = It3.begin();
		while (it3 != It3.end())
		{
			cout << *it3 << " ";
			++it3;
		}
		cout << endl;

		It3.pop_front();
		list<int>::iterator it4 = It3.begin();
		while (it4 != It3.end())
		{
			cout << *it4 << " ";
			++it4;
		}
	}
}